package me.eg.third;

import java.util.*;

/**
 * 210. 课程表 II
 * <p>
 * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
 * <p>
 * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 * <p>
 * 链接：https://leetcode-cn.com/problems/course-schedule-ii
 */
public class FindOrder {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> to = new HashMap<>(); // 出边数组
        int[] inDeg = new int[numCourses]; // 每个点的入度
        // 初始化出边数组
        for (int[] pre : prerequisites) {
            List<Integer> toB = to.getOrDefault(pre[1], new ArrayList<>());
            toB.add(pre[0]);
            to.put(pre[1], toB);
            inDeg[pre[0]]++;
        }

        int[] lessons = new int[numCourses];
        int cnt = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            // 入度 = 0 的点入队
            // 等价于没有先修课可以进入学习
            if (inDeg[i] == 0) queue.offer(i);
        }

        while (!queue.isEmpty()) {
            int c = queue.poll(); // 学完出队
            lessons[cnt++] = c; // 加入已修课程
            List<Integer> nextCourse = to.get(c);
            if (nextCourse != null) {
                for (int y : nextCourse) {
                    inDeg[y]--; // 学完一门先修课，入度减一
                    if (inDeg[y] == 0) queue.offer(y); // 所有先修课都修完，可以进入学习(入队)
                }
            }
        }

        // 已修课程 = 课程总数，表示可以完成所有课程
        if (cnt == numCourses) return lessons;
        return new int[]{};
    }
}
